Vòng lặp đầu tiên Thuật_toán_Grover

Từ định nghĩa, ta có bước khởi tạo

U s = 2 | s ⟩ ⟨ s | − I {\displaystyle U_{s}=2\left|s\right\rangle \left\langle s\right|-I} ,

Uω có thể được biểu diễn theo cách:

U ω = I − 2 | ω ⟩ ⟨ ω | {\displaystyle U_{\omega }=I-2\left|\omega \right\rangle \left\langle \omega \right|} .

Các bước sau cho thấy những gì xảy ra trong vòng lặp đầu tiên: ⟨ ω | s ⟩ = ⟨ s | ω ⟩ = 1 N {\displaystyle \langle \omega |s\rangle =\langle s|\omega \rangle ={\frac {1}{\sqrt {N}}}} .

⟨ s | s ⟩ = N 1 N ⋅ 1 N = 1 {\displaystyle \langle s|s\rangle =N{\frac {1}{\sqrt {N}}}\cdot {\frac {1}{\sqrt {N}}}=1} . U ω | s ⟩ = ( I − 2 | ω ⟩ ⟨ ω | ) | s ⟩ = | s ⟩ − 2 | ω ⟩ ⟨ ω | s ⟩ = | s ⟩ − 2 N | ω ⟩ {\displaystyle U_{\omega }|s\rangle =(I-2|\omega \rangle \langle \omega |)|s\rangle =|s\rangle -2|\omega \rangle \langle \omega |s\rangle =|s\rangle -{\frac {2}{\sqrt {N}}}|\omega \rangle } . U s ( | s ⟩ − 2 N | ω ⟩ ) = ( 2 | s ⟩ ⟨ s | − I ) ( | s ⟩ − 2 N | ω ⟩ ) = 2 | s ⟩ ⟨ s | s ⟩ − | s ⟩ − 4 N | s ⟩ ⟨ s | ω ⟩ + 2 N | ω ⟩ = {\displaystyle U_{s}(|s\rangle -{\frac {2}{\sqrt {N}}}|\omega \rangle )=(2|s\rangle \langle s|-I)(|s\rangle -{\frac {2}{\sqrt {N}}}|\omega \rangle )=2|s\rangle \langle s|s\rangle -|s\rangle -{\frac {4}{\sqrt {N}}}|s\rangle \langle s|\omega \rangle +{\frac {2}{\sqrt {N}}}|\omega \rangle =} = 2 | s ⟩ − | s ⟩ − 4 N ⋅ 1 N | s ⟩ + 2 N | ω ⟩ = | s ⟩ − 4 N | s ⟩ + 2 N | ω ⟩ = N − 4 N | s ⟩ + 2 N | ω ⟩ {\displaystyle =2|s\rangle -|s\rangle -{\frac {4}{\sqrt {N}}}\cdot {\frac {1}{\sqrt {N}}}|s\rangle +{\frac {2}{\sqrt {N}}}|\omega \rangle =|s\rangle -{\frac {4}{N}}|s\rangle +{\frac {2}{\sqrt {N}}}|\omega \rangle ={\frac {N-4}{N}}|s\rangle +{\frac {2}{\sqrt {N}}}|\omega \rangle } .

Sau khi 2 toán tử ( U ω {\displaystyle U_{\omega }} and U s {\displaystyle U_{s}} ) được sử dụng, giá trị cần tìm đã tăng từ | ⟨ ω | s ⟩ | 2 = 1 / N {\displaystyle \left|\langle \omega |s\rangle \right|^{2}=1/N} đến | ⟨ ω | U s U ω s ⟩ | 2 ≈ 9 / N {\displaystyle \left|\langle \omega |U_{s}U_{\omega }s\rangle \right|^{2}\approx 9/N} .